// 用后序遍历和中序遍历序列构造二叉树

// 思路：每次从后序遍历的数组中pop出根节点值，然后从中序遍历数组中找出该索引的，这可以左右子树的长度，从而递归构造
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小

function buildTree(inorder , postorder) {
    if (!postorder.length) {
        return null
    }
    let rootVal = postorder.pop()
    let root = new TreeNode(rootVal)
    let index = inorder.indexOf(rootVal)
    root.left = buildTree(inorder.slice(0, index), postorder.slice(0, index))
    root.right = buildTree(inorder.slice(index + 1), postorder.slice(index))
    return root
}

function TreeNode(val) {
    this.val = val
    this.left = null
    this.right = null
}

let inorder = [9,3,15,20,7]
let postorder = [9,15,7,20,3]
console.log(buildTree(inorder, postorder))